package argo.hot100.recall;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {

    public List<String> generateParenthesis(int n) {

        List<String> res = new ArrayList<>();
        backTrace(n, 0, 0, res, new StringBuffer());
        return res;
    }

    public void backTrace(int n, int left, int right, List<String> res, StringBuffer subres) {


        if (subres.length() == 2 * n) {
            res.add(subres.toString());
            return;
        }
        if (left < n) {
            subres.append('(');
            //System.out.println(1 + subres.toString());
            backTrace(n, left + 1, right, res, subres);
            subres.deleteCharAt(subres.length() - 1);
            //System.out.println(11 + subres.toString());
        }
        if (right < left) {
            subres.append(')');
            //System.out.println(2 + subres.toString());
            backTrace(n, left, right + 1, res, subres);
            subres.deleteCharAt(subres.length() - 1);
           // System.out.println(22 + subres.toString());
        }
    }

}

/**
recall stack
 1(
 1((
 1(((
 2((()
 2((())
 2((()))
 22((())
 22((()
 22(((
 11((
 2(()
 1(()(
 2(()()
 2(()())
 22(()()
 22(()(
 11(()
 2(())
 1(())(
 2(())()
 22(())(
 11(())
 22(()
 22((
 11(
 2()
 1()(
 1()((
 2()(()
 2()(())
 22()(()
 22()((
 11()(
 2()()
 1()()(
 2()()()
 22()()(
 11()()
 22()(
 11()
 22(
 11
 */
